#include "cfg.h"
#include <algorithm>
#include <queue>

void BasicBlock::addPreds(int i){
	preds.push_back(i);
}

void BasicBlock::addSuccs(int i){
	succs.push_back(i);
}

void BasicBlock::resetLiveness(){
	for(int i = 0 ; i < lives.size(); i++){
		lives[i].clear();	
	}

	for(int i = 0 ; i < defs.size(); i++){
		defs[i].clear();	
	}

	for(int i = 0 ; i < uses.size(); i++){
		uses[i].clear();	
	}
}

void CFG::resetLiveness(){
	map<int, BasicBlock *>::iterator it;
	for(it = nodes.begin(); it != nodes.end(); it++){
		it->second->resetLiveness();
	}
}

bool CFG::build(int start){
	set<int> ins;

	int i = start;
	while(i < is.size() && is[i].opt != ENTER){
		if(is[i].opt == ENTRYPC)
			isMain = true;
		i++;
	}

	if(i < is.size())
		entry = i;
	else
		return false;

	while(i < is.size() && is[i].opt != RET){
		switch(is[i].opt){
			case BR:
				ins.insert(is[i].param1.value);
				ins.insert(i+1);
				break;
			case BLBC: 
			case BLBS: 
				ins.insert(is[i].param2.value);
				ins.insert(i+1);
				break;
			case CALL: 
				ins.insert(i+1);
				break;
		}
		i++;
	}

	if(i < is.size())
		end = i;
	else
		return false;

	ins.insert(entry);

	set<int>::iterator it, nit;
	it = nit = ins.begin();
	nit++;
	while(nit != ins.end()){
		nodes.insert(pair<int, BasicBlock *>(*it, new BasicBlock(*it, *nit - 1)));
		it++;
		nit++;
	}

	nodes.insert(pair<int, BasicBlock *>(*it, new BasicBlock(*it, end)));

	map<int, BasicBlock *>::iterator mit;
	mit = nodes.begin();
	while(mit != nodes.end()){
		int in = (*mit).first;
		int out = nodes[in]->out;
		int des;
		switch(is[out].opt){
				case BR:
					des = is[out].param1.value;
					nodes[in]->addSuccs(des);
					nodes[des]->addPreds(in);
					mit++;
					break;
				case BLBC: 
				case BLBS:
					des = is[out].param2.value;
					nodes[in]->addSuccs(des);
					nodes[des]->addPreds(in);
				default:
					mit++;
					if(mit!= nodes.end()){
						nodes[in]->addSuccs(out+1);
						nodes[out+1]->addPreds(in);
					}
					break;
		}
	}

	return true;
}

void CFG::output(ostream& o){
	o<<"Function: "<<entry<<endl;
	map<int, BasicBlock *>::iterator it;
	o<<"Basic blocks:";
	for(it = nodes.begin(); it != nodes.end(); it++){
		o<<" "<< (*it).first;
	}
	o<<endl;
	o<<"CFG:"<<endl;
	for(it = nodes.begin(); it != nodes.end(); it++){
		int in = (*it).first;
		o<<in<<" ->";
		if(nodes[in]->succs.size() == 1){
			o<<" "<<nodes[in]->succs[0];
		}
		if(nodes[in]->succs.size() == 2){
			int i = nodes[in]->succs[0] < nodes[in]->succs[1] ? 0:1;
			o<<" "<<nodes[in]->succs[i]<<" "<<nodes[in]->succs[1-i];
		}
		o<<endl;
	}
	/*
	o<<"CFG(backward):"<<endl;
	for(it = nodes.begin(); it != nodes.end(); it++){
	int in = (*it).first;
	o<<in<<" ->";
	for(int i = 0; i < nodes[in]->preds.size(); i++){
	o<<" "<<nodes[in]->preds[i];
	}
	o<<endl;
	}*/
}

//Implements Gabow's Algorithm
void CFG::findSCR(){
	map<int, BasicBlock *>::iterator it;
	map<int, int> ordering;
	set<int> assigned;
	int c = 0;
	int cur_scr = 0;
	stack<int> S;
	stack<int> P;
	BasicBlock* cur;

	for(it = nodes.begin(); it != nodes.end(); it++){
		cur = (*it).second;
		if(ordering.find(cur->in) == ordering.end())
			findSCRhelper(assigned, ordering, cur->in, c, S, P, cur_scr);
	}

	int size = SCR.size();

	for(int i = 0; i < size; i++){
		if(SCR[i].size() <= 1){
			SCR.erase(SCR.begin() + i);
			i--;
			size--;
		}
		else
			sort(SCR[i].begin(), SCR[i].end());
	}

	sort(SCR.begin(), SCR.end());
}

//Recursive helper
void CFG::findSCRhelper(set<int>& assigned, map<int, int>& ordering, int current, int& c, stack<int>& S, stack<int>& P, int& cur_scr){
	BasicBlock* cur = nodes[current];

	ordering.insert(pair<int,int>(current, c));
	c++;
	S.push(current);
	P.push(current);
	for(int i = 0; i < cur->succs.size(); i++){
		if(ordering.find(cur->succs[i]) == ordering.end())
			findSCRhelper(assigned, ordering, cur->succs[i], c, S, P, cur_scr);
		else{
			if(!P.empty() && (assigned.find(cur->succs[i]) == assigned.end())){
				while(ordering[cur->succs[i]] < ordering[P.top()]){
					P.pop();
				}
			}
		}
	}

	if(!P.empty() && !S.empty()){
		if(P.top() == current){
			while(S.top() != current){
				SCR[cur_scr].push_back(S.top());
				assigned.insert(S.top());
				S.pop();
			}
			SCR[cur_scr].push_back(S.top());
			assigned.insert(S.top());
			S.pop();
			P.pop();
			cur_scr++;
			SCR.push_back(vector<int>());
		}
	}
}

void CFG::printSCR(ostream& o){
	o<<"Function: "<<entry<<endl;
	map<int, BasicBlock *>::iterator it;
	o<<"Basic blocks:";
	for(it = nodes.begin(); it != nodes.end(); it++){
		o<<" "<< (*it).first;
	}
	o << endl;

	o << "SCR: ";

	//for(int i = SCR.size() - 1; i >= 0; i--){
	//	for(int j = 0; j < SCR[i].size(); j++){
	//		o << SCR[i][j] << " " ;
	//	}
	//	o << endl;
	//}

	for(int i = 0; i < SCR.size(); i++){
		for(int j = 0; j < SCR[i].size(); j++){
			o << SCR[i][j] << " " ;
		}
		o << endl;
	}

	if(SCR.size() == 0)
		o << endl;
}

//find the definitions in each block that may reach out of it
void CFG::findDefinitions(){
	map<int, BasicBlock *>::iterator it;
	map<string, set<int> >::iterator it2;
	BasicBlock* block;
	int line;
	const Instr* inst;

	line = 0;

	for(it = nodes.begin(); it != nodes.end(); it++){
		line = (*it).first;
		block = (*it).second;
		while(line <= block->out){
			//std::cout << "la: " << line << std::endl;
			//line++;
			inst = &(is[line]);
			if(inst->opt == MOVE && inst->param2.type == LOCAL_VAR){
				block->definitions[inst->param2.literal].clear();
				block->definitions[inst->param2.literal].insert(line);
				block->outDefinitions[inst->param2.literal].clear();
				block->outDefinitions[inst->param2.literal].insert(line);
			}
			else if(inst->opt == ADD && ((inst->param1.type == ADDR_OFFSET && inst->param2.type == GP) || 
										 (inst->param1.type == GP && inst->param2.type == ADDR_OFFSET)  )){
				const Instr* nextInst = &(is[line+1]);
				if(nextInst->opt == STORE && nextInst->param2.value == line){
					block->definitions[(inst->param1.literal + "_base")].clear();
					block->definitions[(inst->param1.literal + "_base")].insert(line);
					block->outDefinitions[inst->param1.literal + "_base"].clear();
					block->outDefinitions[inst->param1.literal + "_base"].insert(line);
				}
			}
			else if(inst->opt == CALL){
				for(it2 = block->definitions.begin(); it2 != block->definitions.end(); it2++){
					string var_name = (*it2).first;
					if(var_name.find("_base") != string::npos){
						block->definitions[var_name].clear();
					}
				}

				for(it2 = block->outDefinitions.begin(); it2 != block->outDefinitions.end(); it2++){
					string var_name = (*it2).first;
					if(var_name.find("_base") != string::npos){
						block->outDefinitions[var_name].clear();
					}
				}
			}

			line++;
		}
	}
}

//Performs reaching definition analysis
//Uses a worklist
void CFG::reachingDefinitions(queue<BasicBlock*>& workList, set<int>& doneList){
	findDefinitions(); //find the definitions in the blocks
	BasicBlock* block;
	map<int, BasicBlock *>::iterator it;
	map<string, set<int> >::iterator it2;
	map<string, set<int> >::iterator def1;
	const Instr* inst1;
	const Instr* inst2;
	int line;
	set<int> lines;

	while(!workList.empty()){
		block = workList.front();
		bool changed = false;

		for(int i = 0; i < block->preds.size(); i++){
			BasicBlock* pred = (*(nodes.find(block->preds[i]))).second;

			for(it2 = pred->outDefinitions.begin(); it2 != pred->outDefinitions.end(); it2++){
				string variable = (*it2).first;
				lines = (*it2).second;
				if(lines.size() > 0){
					def1 = block->definitions.find(variable);
	
					//if we don't have a definition that kills the previous definitions, then insert them in the out set
					if(def1 == block->definitions.end()){
						int orig_size = block->outDefinitions[variable].size();
						block->outDefinitions[variable].insert(lines.begin(), lines.end());
						if(orig_size != block->outDefinitions[variable].size()){
							changed = true;
						}
					}
	
					block->predDefinitions[variable].insert(lines.begin(), lines.end());
				}
			}
		}

		//if block has changed, add successors to the workList if they aren't already on it
		if(changed){
			for(int i = 0; i < block->succs.size(); i++){
				set<int>::iterator element = doneList.find(block->succs[i]);
				if(element != doneList.end()){
					BasicBlock* pushBlock = (*(nodes.find(block->succs[i]))).second;
					workList.push(pushBlock);
					doneList.erase(element);
				}
			}
		}

		workList.pop();
		doneList.insert(block->in);
	}
}

//simple constant propagation using reaching definitions
void CFG::scp(){
	int propagated = 0;
	BasicBlock* block;
	map<int, BasicBlock *>::iterator it;
	map<string, set<int> >::iterator it2;
	int line;
	int reg;
	Instr* inst;
	Instr* nextInst;
	Instr* defInst;
	set<int> doneListSCP;
	set<int> doneListR;
	queue<BasicBlock *> workListSCP;
	queue<BasicBlock *> workListR;
	
	for(it = nodes.begin(); it != nodes.end(); it++){
		workListR.push((*it).second);
		workListSCP.push((*it).second);
	}
	reachingDefinitions(workListR, doneListR);//perform reaching definitions analysis
	
	//for(it = nodes.begin(); it != nodes.end(); it++){
	//	block = (*it).second;
	while(!workListSCP.empty()){
		block = workListSCP.front();
		map<string, set<int> > curDefinitions(block->predDefinitions); //definitions at the current line;

		bool changed = false;

		for(line = block->in; line <= block->out; line++){
			inst = &(is[line]);
			nextInst = &(is[line+1]);

			if (inst->opt == NOP){
				//do nothing
			}
			else if (inst->opt == ADD){
				propagate(line, inst, curDefinitions, propagated, changed);

				//check if this is a global variable being addressed and modified
				if((inst->param1.type == ADDR_OFFSET && inst->param2.type == GP) || (inst->param1.type == GP && inst->param2.type == ADDR_OFFSET)){
					if(nextInst->opt == STORE && nextInst->param2.value == line && nextInst->param2.type == REG){
						curDefinitions[inst->param1.literal + "_base"].clear();
						curDefinitions[inst->param1.literal + "_base"].insert(line);
					}
				}
			}
			else if (inst->opt == SUB || inst->opt == MUL || inst->opt == DIV || inst->opt == MOD
				  || inst->opt == NEG || inst->opt == CMPEQ || inst->opt == CMPLE || inst->opt == CMPLT){

				propagate(line, inst, curDefinitions, propagated, changed);
			}
			else if (inst->opt == BR){
				//do nothing
			}
			else if (inst->opt == BLBC){
				//do nothing
			}
			else if (inst->opt == BLBS){
				//do nothing
			}
			else if (inst->opt == CALL){
				//kill all global variable definitions since we don't how the function being called will modify them
				for(it2 = curDefinitions.begin(); it2 != curDefinitions.end(); it2++){
					string var_name = (*it2).first;
					if(var_name.find("_base") != string::npos){
						curDefinitions[var_name].clear();
					}
				}
			}
			else if (inst->opt == LOAD || inst->opt == STORE){
				propagate(line, inst, curDefinitions, propagated, changed);
			}
			else if (inst->opt == MOVE){
				propagate(line, inst, curDefinitions, propagated, changed);

				//check if this is a local varible being modified
				if(inst->param2.type == LOCAL_VAR){
					curDefinitions[inst->param2.literal].clear();
					curDefinitions[inst->param2.literal].insert(line);
				}
			}
			else if (inst->opt == READ){
				//do nothing
			}
			else if (inst->opt == WRITE){
				propagate(line, inst, curDefinitions, propagated, changed);
			}
			else if (inst->opt == WRL){
				//do nothing
			}
			else if (inst->opt == PARAM){
				propagate(line, inst, curDefinitions, propagated, changed);
			}
			else if (inst->opt == ENTER){
				//do nothing
			}
			else if (inst->opt == RET){
				//do nothing
			}
			else if (inst->opt == ENTRYPC){
				//do nothing
			}
			else{
				//do nothing
			}
		}
		
		if(changed){
			for(int i = 0; i < block->succs.size(); i++){
				set<int>::iterator element = doneListSCP.find(block->succs[i]);
				BasicBlock* pushBlock = (*(nodes.find(block->succs[i]))).second;
				workListR.push(pushBlock);
				pushBlock->predDefinitions.clear();
				if(element != doneListSCP.end()){
					workListSCP.push(pushBlock);
					doneListSCP.erase(element);
				}
			}
			reachingDefinitions(workListR, doneListR);
		}

		workListSCP.pop();
		doneListSCP.insert(block->in);
	}

	num_propagated = propagated;
}

void CFG::propagate(int line, Instr* inst, map<string, set<int> >& curDefinitions, int& propagated, bool& changed){
	Instr* defInst;
	map<string, set<int> >::iterator it2;
	int reg;
	set<int> defLines;
	set<int>::iterator set_it;

	//Check if this is a local variable and propagate if it is possible
	if(inst->param1.type == LOCAL_VAR){
		bool do_propagation = true;
		it2 = curDefinitions.find(inst->param1.literal);
		if(it2 != curDefinitions.end()){
			defLines = (*it2).second;
			if(defLines.size() == 0){
				//no previous definitions
				do_propagation = false;
			}
			else if(defLines.size() > 1){
			//if more than one definition, check if all are the same constant
				Instr* inst1 = &(is[*(defLines.begin())]);
				Instr* inst2;
				if(inst1->opt == MOVE && inst1->param1.type == CONST){
					for(set_it = defLines.begin()++; set_it != defLines.end(); set_it++){
						inst2 = &(is[*set_it]);
						if(inst2->param1.type != CONST || (inst1->param1.value != inst2->param1.value)){
							do_propagation = false;
							break;
						}
					}
				}
				else
					do_propagation = false;
			}
	
			if(do_propagation){
				defInst = &(is[*(defLines.begin())]);
				if(defInst->opt == MOVE && defInst->param1.type == CONST){
					inst->param1.type = CONST;
					inst->param1.value = defInst->param1.value;
					inst->param1.literal = "";
					propagated++;
					changed = true;
				}
			}
		}
	}

	if(inst->param2.type == LOCAL_VAR && inst->opt != MOVE){
		bool do_propagation = true;
		it2 = curDefinitions.find(inst->param2.literal);
		if(it2 != curDefinitions.end()){
			defLines = (*it2).second;
	
			if(defLines.size() == 0){
				//no previous definitions
				do_propagation = false;
			}
			else if(defLines.size() > 1){
			//if more than one definition, check if all are the same constant
				Instr* inst1 = &(is[*(defLines.begin())]);
				Instr* inst2;
	
				if(inst1->opt == MOVE && inst1->param1.type == CONST){
					for(set_it = defLines.begin()++; set_it != defLines.end(); set_it++){
						inst2 = &(is[*set_it]);
						if(inst2->param1.type != CONST || (inst1->param1.value != inst2->param1.value)){
							do_propagation = false;
							break;
						}
					}
				}
				else
					do_propagation = false;
			}
	
			if(do_propagation){
				defInst = &(is[*(defLines.begin())]);
				if(defInst->opt == MOVE && defInst->param1.type == CONST){
					inst->param2.type = CONST;
					inst->param2.value = defInst->param1.value;
					inst->param2.literal = "";
					propagated++;
					changed = true;
				}
			}
		}
	}

	//Check if this is referencing a global variable and propagate it if it is possible
	if(inst->param1.type == REG){
		reg = inst->param1.value;
		defInst = &(is[reg]);
		if(defInst->opt == LOAD && defInst->param1.type == REG){
			reg = defInst->param1.value;
			defInst = &(is[reg]);
			if(defInst->opt == ADD && defInst->param1.type == ADDR_OFFSET && defInst->param2.type == GP){
				it2 = curDefinitions.find(defInst->param1.literal + "_base");
				if(it2 != curDefinitions.end()){
					defLines = (*it2).second;
					bool do_propagation = true;
					if(defLines.size() == 0){
						//no previous definitions
						do_propagation = false;
					}
					else if(defLines.size() > 1){
						//if more than one definition, check if all are the same constant
						Instr* inst1 = &(is[*(defLines.begin()) + 1]);
						Instr* inst2;
			
						if(inst1->opt == STORE && inst1->param1.type == CONST){
							for(set_it = defLines.begin()++; set_it != defLines.end(); set_it++){
								inst2 = &(is[*set_it + 1]);
								if(inst2->param1.type != CONST || (inst1->param1.value != inst2->param1.value)){
									do_propagation = false;
									break;
								}
							}
						}
						else
							do_propagation = false;
					}
	
					if(do_propagation){
						defInst = &(is[*(defLines.begin()) + 1]);
						if(defInst->opt == STORE && defInst->param1.type == CONST){
							inst->param1.type = CONST;
							inst->param1.value = defInst->param1.value;
							inst->param1.literal = "";
							propagated++;
							changed = true;
						}
					}
				}
			}
		}
	}

	if(inst->param2.type == REG){
		reg = inst->param2.value;
		defInst = &(is[reg]);
		if(defInst->opt == LOAD && defInst->param1.type == REG){
			reg = defInst->param1.value;
			defInst = &(is[reg]);
			if(defInst->opt == ADD && defInst->param1.type == ADDR_OFFSET && defInst->param2.type == GP){
				it2 = curDefinitions.find(defInst->param1.literal + "_base");
				if(it2 != curDefinitions.end()){
					defLines = (*it2).second;
					bool do_propagation = true;
					if(defLines.size() == 0){
						//no previous definitions
						do_propagation = false;
					}
					else if(defLines.size() > 1){
						//if more than one definition, check if all are the same constant
						Instr* inst1 = &(is[*(defLines.begin()) + 1]);
						Instr* inst2;
			
						if(inst1->opt == STORE && inst1->param1.type == CONST){
							for(set_it = defLines.begin()++; set_it != defLines.end(); set_it++){
								inst2 = &(is[*set_it + 1]);
								if(inst2->param1.type != CONST || (inst1->param1.value != inst2->param1.value)){
									do_propagation = false;
									break;
								}
							}
						}
						else
							do_propagation = false;
					}
	
					if(do_propagation){
						defInst = &(is[*(defLines.begin()) + 1]);
						if(defInst->opt == STORE && defInst->param1.type == CONST){
							inst->param2.type = CONST;
							inst->param2.value = defInst->param1.value;
							inst->param2.literal = "";
							propagated++;
							changed = true;
						}
					}
				}
			}
		}
	}
}

void CFG::printSCP(ostream& o){
	o << "Function: " << entry << endl;
	o << "Number of constants propagate: " << num_propagated << endl;
}

void CFG::calDefUse(){
	map<int, BasicBlock * >::iterator it;
	BasicBlock * b;
	for(it = nodes.begin(); it != nodes.end(); it++){
		b = (*it).second;
		for(int i = b->in; i <= b->out; i++){
			b->def(i).clear();
			b->use(i).clear();
			const Operator& op = is[i].opt;
			const Param& p1 = is[i].param1;
			const Param& p2 = is[i].param2;

			stringstream ss;

			switch(op){//def
					case ADD:
					case SUB:
					case MUL:
					case DIV:
					case MOD:
					case NEG:
					case CMPEQ:
					case CMPLE:
					case CMPLT:
					case LOAD:
					case READ: ss.str(""); ss<<"r"<<i; b->def(i).insert(ss.str()); break;
					case MOVE: 
						ss.str(""); ss<<"r"<<i;
						b->def(i).insert(ss.str());

						if(p2.type == REG){
							ss.str(""); ss<<"r"<<p2.value;
							b->def(i).insert(ss.str());
						}
						else if(p2.type == LOCAL_VAR) 
							b->def(i).insert(p2.literal);
						break;
			}

			//use
			if(p1.type == LOCAL_VAR)
				b->use(i).insert(p1.literal);
			else if(p1.type == REG){
				ss.str(""); ss<<"r"<<p1.value;
				b->use(i).insert(ss.str());
			}

			if(p2.type == LOCAL_VAR && op != MOVE)
				b->use(i).insert(p2.literal);
			else if(p2.type == REG && op != MOVE){
				ss.str(""); ss<<"r"<<p2.value;
				b->use(i).insert(ss.str());
			}
		}
	}
}

void CFG::liveness(){
	resetLiveness();
	calDefUse();
	queue<BasicBlock *> worklist;
	BasicBlock * block;
	map<int, BasicBlock *>::reverse_iterator rit;
	//init work list
	for(rit = nodes.rbegin(); rit != nodes.rend(); rit++){
		worklist.push((*rit).second);
	}

	while(!worklist.empty()){
		block = worklist.front();
		bool changed = false;
		block->bOut().clear();
		for(int i = 0 ; i < block->succs.size(); i++){//out[b] = U in[succ]
			BasicBlock * succ = nodes[block->succs[i]];
			block->bOut().insert(succ->bIn().begin(), succ->bIn().end());
		}

		set<string> oldin = block->bIn();

		for(int i = block->out; i >= block->in; i--){//in[i] = (out[i] - def[i]) U use[i]
			block->iIn(i).clear();
			block->iIn(i) = block->iOut(i);
			set<string>::iterator dit, uit;
			for(dit = block->def(i).begin(); dit != block->def(i).end(); dit++){
				block->iIn(i).erase(*dit);
			}

			for(uit = block->use(i).begin(); uit != block->use(i).end(); uit++){
				block->iIn(i).insert(*uit);
			}
		}

		//test whether livein changed? 
		if(block->bIn().size() != oldin.size())
			changed = true;
		else{
			set<string>::iterator it;
			for(it = oldin.begin(); it != oldin.end(); it++){
				if(block->bIn().find(*it) == block->bIn().end())
					changed = true;
			}
		}

		if(changed){
			for(int i = 0; i < block->preds.size(); i++)
				worklist.push(nodes[block->preds[i]]);
		}

		worklist.pop();

	}
}

bool CFG::dse(){

	int ein = 0;
	int eout = 0;
	bool changed = false;

	map<int, BasicBlock *>::iterator it;
	BasicBlock * b;
	set<string>::iterator dit;
	for(it = nodes.begin(); it != nodes.end(); it++){
		b = (*it).second;
		for(int i = b->in; i <= b->out; i++){
			if(!b->def(i).empty()){
				for(dit = b->def(i).begin(); dit != b->def(i).end(); dit++){
					if(b->iOut(i).find(*dit) != b->iOut(i).end())
						break;
				}
				if(dit == b->def(i).end()){//dead code
					isInSCR(i)? dseInSCR++ : dseOutSCR++;
					is[i].opt = UNDEF; //mark for removal
					is[i].param1.type = NA;
					is[i].param2.type = NA;
					changed = true;
				}
			}
		}
	}
	return changed;
}

void CFG::printLiveness(ostream& o){
	o<<"function_"<<entry<<" liveness:"<<endl;

	map<int, BasicBlock *>::iterator it;
	BasicBlock * b;
	set<string>::iterator dit;
	for(it = nodes.begin(); it != nodes.end(); it++){
		b = (*it).second;
		o<<"************************"<<endl;
		for(int i = b->in; i <= b->out; i++){

			for(dit = b->iIn(i).begin(); dit != b->iIn(i).end(); dit++){
				o<<" "<< *dit;
			}
			o<<endl;
			o<<"instr "<<i<<": ";
			is[i].print(cout);
		}

		for(dit = b->bOut().begin(); dit != b->bOut().end(); dit++){
			o<<" "<< *dit;
		}
		o<<endl;
	}
}

bool CFG::isInSCR(int idx){
	for(int i = 0 ; i < SCR.size(); i++){
		for(int j = 0; j < SCR[i].size(); j++){
			if(idx >= nodes[SCR[i][j]]->in && idx <= nodes[SCR[i][j]]->out)
				return true;
		}
	}
	return false;
}
